package sort;

import java.util.Arrays;

/**
 * @Classname HeapSort
 * @Author happytaohaha
 * @Date 2020/2/29
 * @Description 堆排序
 * 1. 讲究从 len/2 开始，因为这个是最后一个有子节点的节点
 * 2. 构建最大堆排出来的是由小到大, 重要操作构建最大堆，和下沉节点
 */
public class HeapSort {

    public static int[] heapSort(int[] array){
        int len = array.length;
        buildHeap(array,len-1);
        for (int i = len - 1; i > 0; i--) {
            //将堆顶元素与末位元素调换
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            //数组长度-1 隐藏堆尾元素
            len--;

            //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
            sink(array, 0, len);
        }
        return array;
    }

    private static void buildHeap(int[] array,int len) {
        for (int i = len / 2; i >= 0; i--) {
            sink(array, i, len);
        }
    }

    //下沉
    private static void sink(int[] array, int index, int len) {
        int leftChild = 2 * index + 1;//左子节点下标
        int rightChild = 2 * index + 2;//右子节点下标
        int present = index;//要调整的节点下标
        //下沉左边
        if (leftChild < len && array[leftChild] > array[present]) {
            present = leftChild;
        }

        //下沉右边
        if (rightChild < len && array[rightChild] > array[present]) {
            present = rightChild;
        }
        //如果下标不相等 证明调换过了
        if (present != index) {
            //交换值
            int temp = array[index];
            array[index] = array[present];
            array[present] = temp;

            //继续下沉
            sink(array, present, len);
        }

    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(heapSort(new int[]{9,8,7,6,5,4,3,2,1})));
    }
}
